#ifndef GRAPH_H
#define GRAPH_H
#include <list>
#include <memory.h>
#include <map>
#include <queue>
#include <set>
#include <cassert>
#include "DFAGraph.h"
#include "types.h"
#include "State.h"



using namespace std;

//NFA图
class Graph {
private:
    int node_index=0; //表示当前有几个节点
    int node_offset=0;//表示新加入的节点，和原来节点的偏移量是多少（两个NFA的编号不同）
    std::map<int, StateNode> nodes;
    map<int,set<int>> close_packet; //所有节点的闭包

    int gf_start_index; //开始状态的集合
    int gf_end_index; //结束状态的集合

    void calcu_close_packet_one_elem(int state_index){
        //为某个元素求关系闭包
        if(close_packet.count(state_index)){
            return ;//已经求过了
        }   
        close_packet[state_index]=move(set<int>{state_index});//自己跟自己肯定是闭包
        for(Transition &tran:nodes[state_index].transitions){
            if(tran.input_char==EPSILON){
                assert(state_index != tran.next_state);
                //是一个关系闭包
                if(!close_packet.count(tran.next_state)){
                    //如果没有的话，递归的求另一个小的
                    calcu_close_packet_one_elem(tran.next_state);
                };
                //合并
                auto &dest=close_packet[state_index];
                auto &src=close_packet[tran.next_state];
                merge(src.begin(), src.end(), dest.begin(), dest.end(), std::inserter(dest, dest.begin()));
 
            }

        }

    }

    void calcu_close_packet(){
        //求出所有状态的关系闭包
        for(auto &node:nodes){
            calcu_close_packet_one_elem(node.first);
        }
    }

    set<int> calcu_close_packet(set<int> &st){
        //求出states里的所有关系闭包，返回一个集合
        if(st.size()==0){
            return set<int>{};
        }else if(st.size()==1){
            return close_packet[*st.begin()];
        }
        else{
            set<int> res;
            for(auto &it :st){
                set<int> &st_one=close_packet[it];
                //合并他们的闭包
                merge(st_one.begin(),st_one.end(),res.begin(),res.end(),inserter(res,res.begin()));
            }
            return res;
        }
    }

public:

    int get_start_state_index(){
        //获取开始状态的下标
        // for(auto &node :nodes){
        //     if(node.second.type==StateType::START){
        //         return node.first;
        //     }
        // }
        // cerr<<"no start state\n";
        // exit(0);
        return gf_start_index;
    }

    int get_end_state_index(){
        //获取结束状态的的下标
        // for(auto &node :nodes){
        //     if(node.second.type==StateType::MATCH){
        //         return node.first;
        //     }
        // }
        // cerr<<"no end state\n";
        // exit(0);
        return gf_end_index;
    }

    bool has_outgoing_edges(int state_index){
        //判断是否有出边
        assert(nodes.count(state_index));
        return !nodes[state_index].transitions.empty();
    }

    bool has_ingoing_edges(int state_index){
        //判断是否有入边
        for(const auto &elem : nodes){
            for( const auto & tra : elem.second.transitions){
                if(tra.next_state==state_index){
                    return true;
                }
            }
        }
        return false;
    }   

    DFAGraph NFAtoDFA() {
        calcu_close_packet();
        // 用一个映射来记录已经处理过的NFA状态集合及其对应的DFA状态ID
        std::map<std::set<int>, int> dfaStates;
        // 新的DFA图
        DFAGraph dfa_graph;
        // 维护NFA状态集合及其对应的DFA状态ID
        std::queue<std::set<int>> statesQueue;


        // 创建DFA的初始状态
        std::set<int> startSet =  close_packet[get_start_state_index()] ; // 假设start_state是NFA的起始状态ID
        statesQueue.push(startSet);
        // dfaStates[startSet] = dfaGraph.createStateNode(StateType::UNMATCH);
        dfa_graph.insert_state(startSet,StateType::START);

        while(!statesQueue.empty()){
            std::set<int> currentState = statesQueue.front();
            statesQueue.pop();

            //dfa_graph.insert_state();
            map<char,set<int>> tranversions; //驱动字符 --> 下一个状态的合集 

            //对于DFA的某个新状态，里面有多个NFA的状态
            for(const int &state_index : currentState){
                for(Transition &tra : nodes[state_index].transitions){
                    if(tra.input_char == EPSILON){
                        continue;
                    }
                    if(tranversions.count(tra.input_char)){
                        //如果存在，将下一个状态字符集加入到tranversions里
                        tranversions[tra.input_char].insert(tra.next_state);
                    }else{
                        tranversions[tra.input_char]=move(set<int>{tra.next_state});
                    }
                }
            }
            //这里的set<char>驱动字符之间就不会有重复了，因为他驱动字符只有一个

            for(auto &elem:tranversions){
                set<int> next_state=move(calcu_close_packet(elem.second));
                if(!dfa_graph.judge_state_exists(next_state)){
                    //不在的话，加入到队列中
                    statesQueue.push(next_state);
                }
                dfa_graph.insert_converstion(currentState,elem.first,next_state);
            }


        }

        // DFA结束状态的下标
        int nfa_end_index=get_end_state_index();
        //所有含有nfa结束状态的都是结束状态
        for(auto &elem:dfa_graph.mp_NFA_DFA){
            if(elem.first.count(nfa_end_index) && dfa_graph.nodes[elem.second].type != StateType::START){
                dfa_graph.nodes[elem.second].type=StateType::MATCH;
            }
        }

        return dfa_graph;
    }

    void update_node_offset(){
        //一定要在合并两个集合之前进行这个操作
        node_offset=node_index;
    }

    int insert_state(){
        //添加一个新状态，返回新状态的下标
        nodes[node_index]=move(StateNode(node_index));
        node_index++;
        return node_index-1;
    }

    int insert_state(StateNode sn){
        //添加一个状态，返回这个状态的下标
        sn.state_id=node_index;
        for(Transition &tran:sn.transitions ){
            tran.next_state+=node_offset;
        }
        nodes[node_index++]=move(sn);
        return node_index-1;
    }

    int move_state(StateNode sn , int index){
        //将sn的值赋值给nodes[index]，状态设置为unmatch
        sn.state_id=index;
        node_offset--;// 确保偏移量一在
        for(Transition &tran:sn.transitions ){
            tran.next_state+=node_offset;
        }
        nodes[index]=move(sn);
        return index;
    }

    void set_state_type(int state_index , StateType st){
        assert(nodes.count(state_index));
        nodes[state_index].type=st;
        if(st==StateType::START){
            gf_start_index=state_index;
        }else if(st==StateType::MATCH){
            gf_end_index=state_index;
        }
    }

    void insert_converstion(int start_index , char chop , int end_index){
        //start-->end  状态，添加一个转换
        if(start_index == end_index && chop==EPSILON){
            return;//自己到自己的空变换，可以不加
        }
        assert( start_index<node_index && end_index < node_index );
        auto &tra=nodes[start_index].transitions;
        tra.push_back(Transition{chop,end_index});
    }

    StateNode & get_state(int index){
        if(nodes.count(index)){
            return nodes[index];
        }else{
            cerr<<"wrong index\n";
            exit(0);
        }
    }
    
    void init_state(){
        //初始化nodes
        nodes.clear();
        node_index=0;
    }

    void init_state(char ch){
        //构造一个变换 从 开始到结束，驱动字符是ch
        init_state();
        int start_index=insert_state();
        int end_index=insert_state();
        set_state_type(start_index,StateType::START);
        set_state_type(end_index,StateType::MATCH);
        insert_converstion(start_index,ch,end_index);
    }

    void init_state(set<char> ch){
        //构造一个变换 从 开始到结束，驱动字符是ch里的元素
        init_state();
        int start_index=insert_state();
        int end_index=insert_state();
        set_state_type(start_index,StateType::START);
        set_state_type(end_index,StateType::MATCH);
        for(auto &c:ch){
            insert_converstion(start_index,c,end_index);
        }


    }

    void union_graph(Graph *gh){
        //进行 | 运算，没优化
        update_node_offset();
        //将另一个图的状态合并到自己这里
        for( const auto &elem:gh->nodes){
            this->insert_state(elem.second);
        }
        //左边
        int start_index=this->insert_state();
        for(auto &elem : this->nodes){
            if(elem.second.type==StateType::START){
                set_state_type(elem.first,StateType::UNMATCH);
                insert_converstion(start_index,EPSILON,elem.first);

            }
        }
        set_state_type(start_index,StateType::START);
        //右边
        int end_index=this->insert_state();
        for(auto &elem : this->nodes){
            if(elem.second.type==StateType::MATCH){
                set_state_type(elem.first,StateType::UNMATCH);
                insert_converstion(elem.first,EPSILON,end_index);

            }
        }
        set_state_type(end_index,StateType::MATCH);
        
    }

    void link_graph(Graph *gh){ 
        //进行 - 运算 没优化
        //记录原来图结束状态，更改结束状态为未结束
        update_node_offset();
        vector<int> first_end_index;
        for(auto &elem:this->nodes){
            if(elem.second.type==StateType::MATCH){
                first_end_index.push_back(elem.first);
                set_state_type(elem.first,StateType::UNMATCH);
            }
        }

        //将另一个图的状态合并到自己这里
        for( auto &elem:gh->nodes){
            if(elem.second.type==StateType::START){
                int next_start_index=this->insert_state(elem.second);
                set_state_type(next_start_index,StateType::UNMATCH);
                for(auto &i:first_end_index){
                    insert_converstion(i,EPSILON,next_start_index);
                }
            }else{
                this->insert_state(elem.second);
            }
            
        }

    }



    void link_graph_b(Graph *gh){
        update_node_offset();
        //进行 - 运算 优化
        if((!this->has_outgoing_edges(this->gf_end_index))&& (!gh->has_ingoing_edges(gh->gf_start_index))){
            //优化部分
            int first_end_index=this->get_end_state_index();
            this->set_state_type(first_end_index,StateType::UNMATCH);
            int second_start_index=gh->get_start_state_index();

            this->move_state(gh->nodes[second_start_index],first_end_index);
            this->set_state_type(first_end_index,StateType::UNMATCH);

            //将剩下的部分移动到first里
            for( auto &elem:gh->nodes){
                if(elem.second.type==StateType::START){
                    continue;               
                }else if(elem.second.type==StateType::MATCH){
                    int end_index=this->insert_state(elem.second);
                    this->set_state_type(end_index,StateType::MATCH);
                }
                else{
                    this->insert_state(elem.second);
                }
                
            }
        }else{
            //正常的
            link_graph(gh);

        }
    }

    void closure_graph(){
        //对自己进行闭包运算
        int start_index=(this->has_ingoing_edges(this->get_start_state_index()))
            ?insert_state():this->get_start_state_index();
        int end_index=(this->has_outgoing_edges(this->get_end_state_index()))
            ?insert_state():this->get_end_state_index();
        for( auto &elem:nodes){
            if(elem.second.type==StateType::START){
                insert_converstion(start_index,EPSILON,elem.first);
                set_state_type(elem.first,StateType::UNMATCH);
            }

            if(elem.second.type==StateType::MATCH){
                insert_converstion(elem.first,EPSILON,end_index);
                insert_converstion(elem.first,EPSILON,start_index);
                set_state_type(elem.first,StateType::UNMATCH);
            }
        }

        set_state_type(start_index,StateType::START);
        set_state_type(end_index,StateType::MATCH);
        insert_converstion(start_index,EPSILON,end_index);
    }

    void plus_closure_graph(){
        //对自己进行正闭包运算
        int start_index=(this->has_ingoing_edges(this->get_start_state_index()))
            ?insert_state():this->get_start_state_index();
        int end_index=(this->has_outgoing_edges(this->get_end_state_index()))
            ?insert_state():this->get_end_state_index();
        for( auto &elem:nodes){
            if(elem.second.type==StateType::START){
                insert_converstion(start_index,EPSILON,elem.first);
                set_state_type(elem.first,StateType::UNMATCH);
            }

            if(elem.second.type==StateType::MATCH){
                insert_converstion(elem.first,EPSILON,end_index);
                insert_converstion(elem.first,EPSILON,start_index);
                set_state_type(elem.first,StateType::UNMATCH);
            }
        }

        set_state_type(start_index,StateType::START);
        set_state_type(end_index,StateType::MATCH);
        //insert_converstion(start_index,EPSILON,end_index);
    }

    void zero_or_one_graph(){
        //对自己进行0或者1个运算
        int start_index=(this->has_ingoing_edges(this->get_start_state_index()))
            ?insert_state():this->get_start_state_index();
        int end_index=(this->has_outgoing_edges(this->get_end_state_index()))
            ?insert_state():this->get_end_state_index();
        for( auto &elem:nodes){
            if(elem.second.type==StateType::START){
                insert_converstion(start_index,EPSILON,elem.first);
                set_state_type(elem.first,StateType::UNMATCH);
            }

            if(elem.second.type==StateType::MATCH){
                insert_converstion(elem.first,EPSILON,end_index);
                //insert_converstion(elem.first,EPSILON,start_index);
                set_state_type(elem.first,StateType::UNMATCH);
            }
        }

        set_state_type(start_index,StateType::START);
        set_state_type(end_index,StateType::MATCH);
        insert_converstion(start_index,EPSILON,end_index);
    }
    
    void display_NFA() {
        cout << "NFA Nodes:" << endl;
        for (const auto& kvp : nodes) {
            cout << "State " << kvp.first << ": ";
            if (kvp.second.type==StateType::MATCH) {
                cout << "(Final State) ";
            }else if (kvp.second.type==StateType::START) {
                cout << "(Start State) ";
            }
            cout << endl;

            cout << "Transitions: " << endl;
            for (const auto& transition : kvp.second.transitions) {
                transition.get_info();
            }
            cout << endl;
        }
        cout<<"----------------------------------------\n";
    }

    void display_DFA_NFA(){
        display_NFA();
        DFAGraph dfa=move(this->NFAtoDFA());
        dfa.display_DFA();
    }

};

#endif